import java.util.*;

public class TestSort {

    public static void main(String[] args) {
        int[] arr = {-23,45,44,23,33,4,2,34,4,23,3,334,34,5,4,3,666666};
        long startTime = System.currentTimeMillis();
//        insertSort(arr);
//        shellSort(arr);
//        selectSort(arr);
//        heapSort(arr);
//        quickSort(arr);
        mergeSort(arr);
//        countingSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println(endTime - startTime);
    }

    /**
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 对于直接插入排序：越有序速度越快
     *          经常使用于：数据量不大，且趋于有序
     * @param arr
     */
    // 直接插入排序
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if (arr[j] > temp){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            // j回退到了 < 0 的情况
            arr[j+1] = temp;
        }
    }
    public static void insertSort2(int[] arr,int start,int end){
        for (int i = 1; i <= end; i++) {
            int temp = arr[i];
            int j = i-1;
            for (; j >= start; j--) {
                if (arr[j] > temp){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            // j回退到了 < 0 的情况
            arr[j+1] = temp;
        }
    }


    /**
     * 时间复杂度：O(n^1.3 - n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定  ----->  看在比较过程中是否发生了跳跃
     * @param arr
     */
    // 希尔排序
    public static void shellSort(int[] arr){
        int gap = arr.length;
        while (gap > 1){
            shell(arr,gap);
            gap /= 2;
        }
        shell(arr,1);
    }
    public static void shell(int[] arr,int gap){
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (arr[j] > temp){
                    arr[j+gap] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap] = temp;
        }
    }


    /**
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param arr
     */
    // 选择排序
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]){
                    min = j;
                }
            }
            swap(arr,i,min);
        }
    }
    public static void selectSortOP(int[] array) {
        int low = 0;
        int high = array.length - 1;
        // [low, high] 表示整个无序区间    
        // 无序区间内只有一个数也可以停止排序了    
        while (low <= high) {
            int min = low;
            int max = low;
            for (int i = low+1; i <= high; i++) {
                if (array[i] < array[min]) {
                    min = i;
                }
                if (array[i] > array[max]) {
                    max = i;
                }
            }
            swap(array, min, low);
            if (max == low) {
                max = min;
            }
            low++;
            swap(array, max, high);
            high--;
        }
    }


    /**
     * 时间复杂度：O(n^lgN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param arr
     */
    // 堆排序
    public static void heapSort(int[] arr){
        createHeap(arr);
        int end = arr.length;
        while (end > 0){
            swap(arr,0,--end);
            shiftDown(arr,0,end);
        }
    }
    public static void createHeap(int[] arr){
        for (int parent = (arr.length-1-1)/2; parent >= 0; parent--) {
            shiftDown(arr,parent,arr.length);
        }
    }
    public static void shiftDown(int[] arr,int parent,int len){
        int child = parent*2 + 1;
        while (child < len){
            if (child + 1 < len && arr[child+1] > arr[child]){
                child++;
            }
            if (arr[parent] < arr[child]){
                swap(arr,parent,child);
                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }
    }


    /**
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param arr
     */
    // 冒泡排序
    public void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                    flag = false;
                }
            }
            if (flag) return;
        }
    }

    /**
     * 时间复杂度： 最好：O(N*lgN)  最坏：O(N^2) --- 顺序或者逆序
     * 空间复杂度： 最好：O(lgN)    最坏：O(N) --- 顺序或者逆序
     * 稳定性：不稳定
     * @param arr
     */
    // 快速排序
    public static void quickSort(int[] arr){
//        quick(arr,0,arr.length-1);
        quickNor(arr,0,arr.length-1);
    }
    public static void quick(int[] arr,int left,int right){
        if (left >= right) return;

        if (right - left <= 5000) insertSort2(arr,left,right);

        // 优化 1： 在找基准前，使用三数取中法
        int middleIndex = findMiddleIndex(arr,left,right);
        swap(arr,left,middleIndex);

        int pivot = partition(arr,left,right);
        quick(arr,left,pivot-1);
        quick(arr,pivot+1,right);
    }
    public static int partition(int[] arr,int start,int end){
        int temp = arr[start];
        while (start < end){
            while (start < end && arr[end] >= temp){
                end--;
            }
            arr[start] = arr[end];
            while (start < end && arr[start] <= temp){
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = temp;
        return start;
    }
    public static int findMiddleIndex(int[] arr,int start,int end){
        int mid = start + ((end - start) >> 1);
        if (arr[start] < arr[end]){
            if (arr[mid] < arr[start]) return start;
            if (arr[mid] > arr[end]) return end;
            return mid;
        }else if (arr[start] > arr[end]){
            if (arr[mid] > arr[start]) return start;
            if (arr[mid] < arr[end]) return end;
            return mid;
        }else{
            return start;
        }
    }
    /**
     * 非递归快速排序
     * @param arr
     */
    public static void quickNor(int[] arr,int left,int right){
        Stack<Integer> stack = new Stack<>();
        int pivot = partition(arr,0,arr.length-1);
        if (pivot > left + 1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if (pivot > left + 1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();

            pivot = partition(arr,left,right);

            if (pivot > left + 1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if (pivot > left + 1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }


    /**
     * 时间复杂度：O(N * lgN)
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * 稳定的 ---> 插入，冒泡，归并
     * 归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr){
//        mergeSortFunc(arr,0,arr.length-1);
        mergeSortNor(arr);
    }
    private static void mergeSortFunc(int[] arr,int left,int right){
        if (left >= right) return;
        int mid = left + ((right - left) >> 1);
        mergeSortFunc(arr,left,mid);
        mergeSortFunc(arr,mid+1,right);
        merge(arr,left,mid,right);
    }
    public static void merge(int[] arr,int left,int mid,int right){
        int[] ret = new int[right - left + 1];
        int s1 = left;
        int s2 = mid+1;
        int index = 0;
        while (s1 <= mid && s2 <= right){
            if (arr[s1] <= arr[s2]){
                ret[index++] = arr[s1++];
            }else{
                ret[index++] = arr[s2++];
            }
        }
        while (s2 <= right){
            ret[index++] = arr[s2++];
        }
        while (s1 <= mid){
            ret[index++] = arr[s1++];
        }
        // 拷贝ret中的元素放入arr中
        for (int i = 0; i < index; i++) {
            arr[i+left] = ret[i];
        }
    }

    /**
     * 非递归实现归并排序
     * @param arr
     */
    private static void mergeSortNor(int[] arr){
        int gap = 2;// 每组的数据个数
        int lastMid = 0;
        while (gap < arr.length*2){
            for (int i = 0; i < arr.length; i+=gap) {
                int left = i;
                int right = left + gap - 1;
                int mid = (right + left) / 2;
                if (mid >= arr.length){
                    mid = arr.length-1;
                }
                if (right >= arr.length){
                    right = arr.length-1;
                }
                merge(arr,left,mid,right);
                lastMid = mid;
            }
            gap *= 2;
        }
    }


    /**
     * 计数排序
     * 适用于有 n 个数，范围是 0 ~ n
     * 稳定性：稳定
     * @param arr
     */
    public static void countingSort(int[] arr){
        int maxVal = arr[0];
        int minVal = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < minVal) minVal = arr[i];
            if (arr[i] > maxVal) maxVal = arr[i];
        }
        int[] count = new int[maxVal - minVal + 1];
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] - minVal;
            count[index] += 1;
        }// 次数已经统计好了

        // 遍历count数组，写回原数组
        int indexArr = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]-- > 0){
                arr[indexArr++] = i + minVal;
            }
        }
    }

    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
